<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="en">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.3" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16.png?v=5.1.3">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.3" color="#222">





  <meta name="keywords" content="haskell,memoization,lazy-evaluation" />










<meta name="description" content="Haskell 中一种简单的定义 Fibonacci 函数的方式： 123fib 0 = 0fib 1 = 1fib n = fib (n - 1) + fib (n - 2) 看起来很直观，可以和数学上的 Fibonacci 函数定义一一对应。但是每次递归时会调用 fib 函数两次，时间复杂度是指数级的，效率惨不忍睹。   上面的 fib 函数进行了大量的重复运算，我们可以使用 memoizat">
<meta name="keywords" content="haskell,memoization,lazy-evaluation">
<meta property="og:type" content="article">
<meta property="og:title" content="Memoization in Haskell">
<meta property="og:url" content="https://arucil.github.io/2018/memoization-in-haskell/index.html">
<meta property="og:site_name" content="Plodsoft&#39;s Blog">
<meta property="og:description" content="Haskell 中一种简单的定义 Fibonacci 函数的方式： 123fib 0 = 0fib 1 = 1fib n = fib (n - 1) + fib (n - 2) 看起来很直观，可以和数学上的 Fibonacci 函数定义一一对应。但是每次递归时会调用 fib 函数两次，时间复杂度是指数级的，效率惨不忍睹。   上面的 fib 函数进行了大量的重复运算，我们可以使用 memoizat">
<meta property="og:locale" content="en">
<meta property="og:image" content="https://arucil.github.io/images/natural_tree.png">
<meta property="og:updated_time" content="2018-08-23T09:19:14.636Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Memoization in Haskell">
<meta name="twitter:description" content="Haskell 中一种简单的定义 Fibonacci 函数的方式： 123fib 0 = 0fib 1 = 1fib n = fib (n - 1) + fib (n - 2) 看起来很直观，可以和数学上的 Fibonacci 函数定义一一对应。但是每次递归时会调用 fib 函数两次，时间复杂度是指数级的，效率惨不忍睹。   上面的 fib 函数进行了大量的重复运算，我们可以使用 memoizat">
<meta name="twitter:image" content="https://arucil.github.io/images/natural_tree.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.3',
    sidebar: {"position":"left","display":"always","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://arucil.github.io/2018/memoization-in-haskell/"/>





  <title>Memoization in Haskell | Plodsoft's Blog</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Plodsoft's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description">Programming Language Enthusiast</h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
            Tags
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
            Archives
          </a>
        </li>
      
        
        <li class="menu-item menu-item-games">
          <a href="/games" rel="section">
            
            Games
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://arucil.github.io/2018/memoization-in-haskell/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Plodsoft">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="https://avatars0.githubusercontent.com/u/5410312?v=4&s=460">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Plodsoft's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">Memoization in Haskell</h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-08-23T00:00:00+08:00">
                2018-08-23
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/2018/memoization-in-haskell/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count disqus-comment-count"
                        data-disqus-identifier="2018/memoization-in-haskell/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>Haskell 中一种简单的定义 Fibonacci 函数的方式：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div></pre></td><td class="code"><pre><div class="line"><span class="title">fib</span> <span class="number">0</span> = <span class="number">0</span></div><div class="line"><span class="title">fib</span> <span class="number">1</span> = <span class="number">1</span></div><div class="line"><span class="title">fib</span> n = fib (n - <span class="number">1</span>) + fib (n - <span class="number">2</span>)</div></pre></td></tr></table></figure>
<p>看起来很直观，可以和数学上的 Fibonacci 函数定义一一对应。但是每次递归时会调用 <code>fib</code> 函数两次，时间复杂度是指数级的，效率惨不忍睹。  </p>
<p>上面的 <code>fib</code> 函数进行了大量的重复运算，我们可以使用 memoization，把计算结果保存起来，避免重复计算。  </p>
<a id="more"></a>
<p>在命令式编程中这很容易实现，使用一个可变数据结构保存计算结果就行了。Haskell 中虽然没有可变数据结构，但我们可以利用它的 lazy evaluation 特性，把计算结果事先保存在一个 list 中，在需要时再从中取出某个计算结果。</p>
<h2 id="List-based-memo"><a href="#List-based-memo" class="headerlink" title="List-based memo"></a>List-based <code>memo</code></h2><p>一个 <code>memo</code> 函数的简单实现如下：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line"><span class="title">memo</span> :: (<span class="type">Integer</span> -&gt; a) -&gt; <span class="type">Integer</span> -&gt; a</div><div class="line"><span class="title">memo</span> f = (map f [<span class="number">0.</span>.] !!) . fromEnum</div></pre></td></tr></table></figure>
<p><code>memo</code> 函数可以 memoize 任何 <code>Integer</code> 参数的函数。如果需要 memoize 多个参数的函数，可以对函数的每个参数分别进行 memoize。</p>
<p>有了 <code>memo</code> 函数，我们的 <code>fib</code> 函数就可以这样定义：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div></pre></td><td class="code"><pre><div class="line"><span class="title">fibMemo</span> = memo fib'</div><div class="line">  <span class="keyword">where</span></div><div class="line">    fib' <span class="number">0</span> = <span class="number">0</span></div><div class="line">    fib' <span class="number">1</span> = <span class="number">1</span></div><div class="line">    fib' n = fibMemo (n - <span class="number">1</span>) + fibMemo (n - <span class="number">2</span>)</div></pre></td></tr></table></figure>
<p>注意，在 <code>fib&#39;</code> 函数的递归 case 中调用的是 <code>fibMemo</code> 函数，而不是 <code>fib&#39;</code>，这样 <code>fib&#39;</code> 函数才能使用保存的计算结果。</p>
<h2 id="Binary-tree-based-memo"><a href="#Binary-tree-based-memo" class="headerlink" title="Binary-tree-based memo"></a>Binary-tree-based <code>memo</code></h2><p>上面定义的 <code>memo</code> 函数中使用 <code>!!</code> 读取保存的计算结果，时间复杂度是$O(n)$；<code>fibMemo</code> 的时间复杂度是$O(n^2)$，效率略低。我们可以使用二叉树来提高效率。</p>
<p>但是 <code>memo</code> 函数中使用的是一个无限长的自然数 list，我们要如何使用二叉树来表示无限多的自然数呢？</p>
<p>先看看不用 <strong><code>..</code> notation</strong> 的话如何定义自然数 list：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line"><span class="title">naturals</span> = <span class="number">0</span> : map (+ <span class="number">1</span>) naturals</div></pre></td></tr></table></figure>
<p>$0$ 是自然数；对于任何自然数 $N$，$N+1$ 也是自然数。这样我们就定义出了 <code>naturals</code>。注意上面的定义中 <code>naturals</code> 引用了 <code>naturals</code> 本身。</p>
<p>同理，我们也可以定义对应的二叉树：<br>$0$ 是自然数；对于任何自然数$N$，$2N+1$和$2N+2$也是自然数。  </p>
<p>首先定义二叉树的数据结构和 <strong>Functor</strong> instance（也可以使用<code>DeriveFunctor</code>扩展）：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line"><span class="class"><span class="keyword">data</span> <span class="type">Tree</span> a = <span class="type">Node</span> a (<span class="type">Tree</span> <span class="title">a</span>) (<span class="type">Tree</span> <span class="title">a</span>)</span></div><div class="line"></div><div class="line"><span class="class"><span class="keyword">instance</span> <span class="type">Functor</span> <span class="type">Tree</span> <span class="keyword">where</span></span></div><div class="line">  fmap f (<span class="type">Node</span> x l r) = <span class="type">Node</span> (f x) (fmap f l) (fmap f r)</div></pre></td></tr></table></figure>
<p>然后是二叉树版本的 <code>naturals</code>：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line"><span class="title">naturals1</span> = <span class="type">Node</span> <span class="number">0</span> (fmap ((+ <span class="number">1</span>) . (* <span class="number">2</span>)) naturals1) (fmap ((+ <span class="number">2</span>) . (* <span class="number">2</span>)) naturals1)</div></pre></td></tr></table></figure>
<p>生成的二叉树结构如下：<br><img src="/images/natural_tree.png" alt=""></p>
<p>然后定义二叉树的查找函数：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div></pre></td><td class="code"><pre><div class="line">(!!!) :: <span class="type">Tree</span> a -&gt; <span class="type">Integer</span> -&gt; a</div><div class="line"><span class="type">Node</span> x _ _ !!! <span class="number">0</span> = x</div><div class="line"><span class="type">Node</span> _ l r !!! n</div><div class="line">  | odd n = l !!! div n <span class="number">2</span></div><div class="line">  | otherwise = r !!! div (n - <span class="number">2</span>) <span class="number">2</span></div></pre></td></tr></table></figure>
<p><code>!!!</code> 查找的效率是 $O(\log n)$。</p>
<p>接下来我们就可以定义 <code>treeMemo</code>：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line"><span class="title">treeMemo</span> :: (<span class="type">Integer</span> -&gt; a) -&gt; <span class="type">Integer</span> -&gt; a</div><div class="line"><span class="title">treeMemo</span> f = (fmap f naturals !!!)</div></pre></td></tr></table></figure>
<p>和 <code>treeMemo</code> 版本的 <code>fibTreeMemo</code>：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div></pre></td><td class="code"><pre><div class="line"><span class="title">fibTreeMemo</span> = memo fib'</div><div class="line">  <span class="keyword">where</span></div><div class="line">    fib' <span class="number">0</span> = <span class="number">0</span></div><div class="line">    fib' <span class="number">1</span> = <span class="number">1</span></div><div class="line">    fib' n = fibTreeMemo (n - <span class="number">1</span>) + fibTreeMemo (n - <span class="number">2</span>)</div></pre></td></tr></table></figure>
<p><code>fibTreeMemo</code> 的效率是 $O(n \log n)$。</p>
<p>对比一下 <code>fibMemo</code> 和 <code>fibTreeMemo</code> 的运行时间：在我的电脑上，运行 <code>fibMemo 100000</code> 需要 235.5 秒，而 <code>fibTreeMemo 100000</code> 只需要 2.75 秒。</p>
<h2 id="Conclusion"><a href="#Conclusion" class="headerlink" title="Conclusion"></a>Conclusion</h2><p>我们以 Fibonacci 函数为例子，讨论了基于 list 和基于二叉树的 memoization 技术。</p>
<p>但在这里使用 Fibonacci 作为例子并不合适，因为上面定义的 <code>fibTreeMemo</code> 的 $O(n \log n)$ 时间复杂度也不算高效，还有 $O(n)$ 复杂度而且更简洁的方法：</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line"><span class="title">fibLinear</span> = (fibs !!)</div><div class="line">  <span class="keyword">where</span> fibs = <span class="number">0</span> : <span class="number">1</span> : zipWith (+) fibs (tail fibs)</div></pre></td></tr></table></figure>
<p>或者</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line"><span class="title">fibLinear</span> = (fibs !!)</div><div class="line">  <span class="keyword">where</span> fibs = <span class="number">0</span> : scanl (+) <span class="number">1</span> fibs</div></pre></td></tr></table></figure>
<p><code>fibLinear 100000</code> 只需要 0.5 秒。</p>
<p>我们甚至可以利用矩阵乘法来加速 Fibonacci [3]，但这不在本文的讨论范围之内。</p>
<p>在 <code>data-inttrie</code> package [4] 中使用了另一种用二叉树表示自然数的方法，感兴趣的读者可以看一下。</p>
<h2 id="Bibliography"><a href="#Bibliography" class="headerlink" title="Bibliography"></a>Bibliography</h2><p>[1] <a href="https://wiki.haskell.org/Memoization" target="_blank" rel="external">https://wiki.haskell.org/Memoization</a><br>[2] <a href="http://lukahorvat.github.io/programming/2014/11/18/haskell-memoization/" target="_blank" rel="external">http://lukahorvat.github.io/programming/2014/11/18/haskell-memoization/</a><br>[3] <a href="https://www.nayuki.io/page/fast-fibonacci-algorithms" target="_blank" rel="external">https://www.nayuki.io/page/fast-fibonacci-algorithms</a><br>[4] <a href="http://hackage.haskell.org/package/data-inttrie" target="_blank" rel="external">http://hackage.haskell.org/package/data-inttrie</a></p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/Haskell/" rel="tag"># Haskell</a>
          
            <a href="/tags/Memoization/" rel="tag"># Memoization</a>
          
            <a href="/tags/Lazy-evaluation/" rel="tag"># Lazy-evaluation</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2018/cps-transformer-implementation/" rel="next" title="CPS Transformer的实现">
                <i class="fa fa-chevron-left"></i> CPS Transformer的实现
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  
    <div class="comments" id="comments">
      <div id="disqus_thread">
        <noscript>
          Please enable JavaScript to view the
          <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a>
        </noscript>
      </div>
    </div>
  


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            Table of Contents
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            Overview
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="https://avatars0.githubusercontent.com/u/5410312?v=4&s=460"
                alt="Plodsoft" />
            
              <p class="site-author-name" itemprop="name">Plodsoft</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">4</span>
                  <span class="site-state-item-name">posts</span>
                </a>
              </div>
            

            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">7</span>
                  <span class="site-state-item-name">tags</span>
                </a>
              </div>
            

          </nav>

          

          <div class="links-of-author motion-element">
            
          </div>

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#List-based-memo"><span class="nav-number">1.</span> <span class="nav-text">List-based memo</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Binary-tree-based-memo"><span class="nav-number">2.</span> <span class="nav-text">Binary-tree-based memo</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Conclusion"><span class="nav-number">3.</span> <span class="nav-text">Conclusion</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Bibliography"><span class="nav-number">4.</span> <span class="nav-text">Bibliography</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Plodsoft</span>

  
</div>


  <div class="powered-by">Powered by <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a></div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">Theme &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.3</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.3"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.3"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.3"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.3"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.3"></script>



  


  

    
      <script id="dsq-count-scr" src="https://plodsoft.disqus.com/count.js" async></script>
    

    
      <script type="text/javascript">
        var disqus_config = function () {
          this.page.url = 'https://arucil.github.io/2018/memoization-in-haskell/';
          this.page.identifier = '2018/memoization-in-haskell/';
          this.page.title = 'Memoization in Haskell';
        };
        var d = document, s = d.createElement('script');
        s.src = 'https://plodsoft.disqus.com/embed.js';
        s.setAttribute('data-timestamp', '' + +new Date());
        (d.head || d.body).appendChild(s);
      </script>
    

  




	





  










  





  

  

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
